/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 晓星航
 * Date: 2023-11-21
 * Time: 9:02
 */

public class GridTraversal {
    private static final int[][] DIRECTIONS = {{0, -2}, {-1, -1}, {-2, 0}, {-1, 1}, {0, 2}};

    public int findMaxSum(int[][] grid) {
        int n = grid.length;
        int m = grid[0].length;

        int[][] dp = new int[n][m];

        // 初始化最后一行的dp值为方格中对应位置的值
        for (int j = 0; j < m; j++) {
            dp[n - 1][j] = grid[n - 1][j];
        }

        // 从倒数第二行开始逐行计算dp值
        for (int i = n - 2; i >= 0; i--) {
            for (int j = 0; j < m; j++) {
                int maxSum = Integer.MIN_VALUE;

                for (int[] dir : DIRECTIONS) {
                    int newX = i + dir[0];
                    int newY = j + dir[1];

                    if (newX >= 0 && newX < n && newY >= 0 && newY < m) {
                        maxSum = Math.max(maxSum, dp[newX][newY]);
                    }
                }

                dp[i][j] = maxSum + grid[i][j];
            }
        }

        // 找到第一行dp值的最大值即为所求的最大和
        int maxSum = Integer.MIN_VALUE;
        for (int j = 0; j < m; j++) {
            maxSum = Math.max(maxSum, dp[0][j]);
        }

        return maxSum;
    }
}
